Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class $\mathcal{F}$, our algorithm achieves a regret bound of $\widetilde{O}(\mathrm{poly}(dH)\sqrt{T})$ where $d$ is a complexity measure of $\mathcal{F}$ that depends on the eluder dimension~[Russo and Van Roy, 2013] and log-covering numbers, $H$ is the planning horizon, and $T$ is the number interactions with the environment.

In online Inverse Reinforcement Learning (IRL), the learner can collect samples about the dynamics of the environment to improve itsestimate of the reward function. Since IRL suffers from identifiability issues, many theoretical works on online IRL focus on estimating the entire set of rewards that explain the demonstrations, named the feasible reward set. However, none of the algorithms available in literature can scale to problems with large state spaces. In this paper, we focus on the online IRL problem in Linear Markov DecisionProcesses (MDPs). We show that the structure offered by Linear MDPs is not sufficient for efficiently estimating the feasible set when the state space is large.

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class \mathcal{F}, our algorithm achieves a regret bound of \widetilde{O}(\mathrm{poly}(dH)\sqrt{T}) where d is a complexity measure of \mathcal{F} that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, H is the planning horizon, and T is the number interactions with the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.

This assumption is crucial for dynamic programming type of analysis. Although it seems to be just an assumption on the value function class, it actually also implicit makes assumption about the MDP. The difference between the sensitive sampling in this paper and the prior work also need to be discussed more. Moreover, the connection between Lemma 9 and 10 and Proposition 3 and Lemma 2 in [44] also need to be discussed. I think these discussions will be helpful for people to understand the details and digest the proof.

The problem of exploration in RL with function approximation is very important and any advancement on the topic is of interest for the community. The reviewers all agreed about the algorithmic and technical contribution of the paper, in particular the introduction of sensitive sampling and its analysis in the regret proof. This convinced us that the paper deserves acceptance. Nonetheless, I also encourage the authors to improve the current submission. As pointed out by R3, the assumptions used in the paper are quite strong and they may somehow limit the generality of the results.

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class \mathcal{F}, our algorithm achieves a regret bound of \widetilde{O}(\mathrm{poly}(dH)\sqrt{T}) where d is a complexity measure of \mathcal{F} that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, H is the planning horizon, and T is the number interactions with the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.